package DFS;

/**
 *
 * 自己的判断节点是否在环中
 *
 * @Author: dust
 * @Date: 2019/11/18 16:27
 */
public class Huan {

    private Graph G;
    private boolean[] visited;
    private int[] pre;
    private int s;
    private boolean flag;


    public Huan(Graph G, int s) {

        this.G=G;
        this.s=s;
        visited=new boolean[G.V()];
        pre=new int[G.V()];
        for(int i=0;i<pre.length;i++){
            pre[i]=-1;
        }
        flag=dfs(s,s);
    }

    private boolean dfs(int v,int parent){
        visited[v]=true;
        pre[v]=parent;
        for(int w:G.adj(v)){
            if(visited[w]){
                if(pre[v]!=w&&w==s){
                    return true;
                }else{
                    continue;
                }
            }else if(!visited[w]){
               if(dfs(w,v))
                   return true;
            }
        }
        return false;
    }



    public static void main(String[] args) {
        Graph g=new Graph("g.txt");
        for(int i=0;i<7;i++){
            Huan dfs=new Huan(g,i);
            System.out.println(dfs.flag);
        }

    }

}
